﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0125_BuildTree : IAlgorithm
    {
        // 从前序与中序遍历序列构造二叉树

        // 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

        // 提示:
        //  1 <= preorder.length <= 3000
        //  inorder.length == preorder.length
        //  -3000 <= preorder[i], inorder[i] <= 3000
        //  preorder 和 inorder 均 无重复 元素
        //  inorder 均出现在 preorder
        //  preorder 保证 为二叉树的前序遍历序列
        //  inorder 保证 为二叉树的中序遍历序列


        public void Test()
        {
            // 算法参数定义
            //var preorder = new int[] { 3, 9, 20, 15, 7 };
            //var inorder = new int[] { 9, 3, 15, 20, 7 };
            var preorder = new int[] { 4, 1, 3, 2 };
            var inorder = new int[] { 1, 2, 3, 4 };
            // 算法执行与打印
            var res = BuildTree(preorder, inorder);
            Console.WriteLine(res);
        }

        // 算法
        public TreeNode BuildTree(int[] preorder, int[] inorder)
        {
            return BuildTree(preorder.ToList(), inorder.ToList());
        }
        private TreeNode BuildTree(List<int> preorder, List<int> inorder)
        {
            var rootVal = preorder[0];
            var res = new TreeNode(rootVal);
            var rootIndexOfInorder = inorder.IndexOf(rootVal);
            if (rootIndexOfInorder != 0)
                res.left = BuildTree(preorder.Skip(1).Take(rootIndexOfInorder).ToList(),
                    inorder.Take(rootIndexOfInorder).ToList());
            if (rootIndexOfInorder != inorder.Count - 1)
                res.right = BuildTree(preorder.Skip(1 + rootIndexOfInorder).ToList(),
                    inorder.Skip(1 + rootIndexOfInorder).ToList());
            return res;
        }
    }
}
